// 求解最大和次大元素算法
#include<iostream>
#include<vector> 
using namespace std;
#define INF 0x3f3f3f3f // 表示最大的整数

// 被solve调用
void solve1(vector<int>&a, int low, int high, int &max1, int &max2)
{
	// 区间只有一个元素
	if (low==high)
	{
		max1 = a[low];
		max2 = -INF;
	}
	
	// 区间只有两个元素
	else if (low==high-1)
	{
		max1 = max(a[low], a[high]);
		max2 = min(a[low], a[high]);
	}
	
	// 区间有多个元素
	else
	{
		int mid = (low+high) / 2;
		
		// 左区间求lmax1和lmax2
		int lmax1, lmax2;
		solve1(a, low, mid, lmax1, lmax2);
		
		// 右区间求lmax1和lmax2
		int rmax1, rmax2;
		solve1(a,mid+1,high,rmax1,rmax2);
		
		// 合并
		if (lmax1>rmax1)
		{
			max1 = lmax1;
			max2 = max(lmax2, rmax1);	// lmax2,rmax1中求次大元素
		}
		else
		{
			max1 = rmax1;
			max2 = max(lmax1, rmax2);	// lmax1,rmax2中求次大元素
		}
	}
}

// 求a中最大和次大元素
void solve(vector<int>&a, int &max1,int &max2)
{
	solve1(a, 0, a.size()-1, max1, max2);
}

int main()
{
	// 初始化数组
	vector<int> a={1, 3, 3};
	
	// 求最大值、次大值
	int max1, max2;
	solve(a, max1, max2);
	
	// 打印
	printf("max1=%d,max2=%d\n", max1, max2);
	return 0;
}



